1. 社区发现简介
社区，从直观上来看，是指网络中的一些密集群体，每个社区内部的结点间的联系相对紧密，但是各个社区之间的连接相对来说却比较稀疏（图1，当然社区的定义不止有这一种）。这样的社区现象被研究已经很多年了，最早期的记录甚至来自于80年前。
比较经典的社区研究案例包括对空手道俱乐部(karate club),科学家合作网络(Collaboration network) 和斑马群体(zebras) 的社交行为研究等（见图2），其中著名的空手道俱乐部社区已经成为通常检验社区发现算法效果的标准(benchmark)之一。
随着互联网和在线社交网站的兴起，在Twitter,Facebook，Flickr这样的用户生成内容（UCG）网站上使用社区发现的技术已经成为热潮。在这些社区中用户相互的交流与反馈，能为传统的社区带来丰富的内容信息和新的结构，从而使社区发现有了新的发展。
2. 社区发现算法介绍
因为社区发现的算法很多很多，下图列出了比较核心的社区发现算法介绍（在参考1给的目录上稍作修改，包含但不限于，五花八门的太多了）：
对上图所涉及的算法作简单介绍：
2.1 图分割
社区可以看做密集子图结构，使用图分割算法来解决。图分割问题的目标是把图中的节点分成\(g\)个预定大小的群组，这些群组之间的边数目最小，这个问题是NP-hard 的。
2.1.1 二分图
早期的分割都是二分图，社区发现也是基于二分的，遇到多分的情况就把其中一个子图再分割。比较经典的有谱二分法，利用拉普拉斯矩阵的第二小特征值\(\lambda_2\)对社区二分类，这其实是属于谱方法的一种特例。
2.1.2 KL算法
KL算法通过基于贪婪优化的启发式过程把网络分解为2个规模已知的社区。该算法为网络的划分引入一个增益函数，定义为两个社区内部的边数与两个社区边数之间的差，寻求Q的最大划分办法。
2.1.3 最大流算法
基于最大流的算法是G.W.Flake提出的。他给网络加了虚拟源节点\(s\)和终点节点\(t\)，并证明了经过最大流算法之后，包含源点\(s\)的社区恰好满足社区内节点链接比与社区外的链接要多的性质。
2.2 聚类
当社区的边非常密集，数目远大于点时，图分割可能就不太好使了，这时候社区发现可能更接近于聚类。我们把社区发现看做一组内容相似的物体集合，使用聚类算法。和图中的社区发现相比，图中的社区点与点之间可以用边来表示联系的紧密，而聚类中的社区，需要定义点之间的相似度，比如说根据邻接关系定义： \[d_{ij}=\sqrt{\sum_{k\neq i,j}(A_{ik}-A_{jk})^2}\] 其中\(A\)为邻接矩阵，\(i\)和\(j\)的邻居越多，节点相似度越高。 聚类算法和网络发现（聚类相关的）算法可以很容易地互相转化。另外，社区发现可以是局部的，而聚类是全网络的。
2.2.1 层次聚类
层次聚类假设社区是存在层次结构的（其实不一定额，可能是中心结构），计算网络中每一对节点的相似度。 然后分为凝聚法和分裂法两种：
凝聚法：根据相似度从强到弱连接相应节点对，形成树状图（Dendrogram），根据需求对树状图进行横切，获得社区结构。
分裂法：找出相互关联最弱的节点，并删除他们之间的边，通过这样的反复操作将网络划分为越来越小的组件，连通的网络构成社区。
2.2.2 划分聚类/扁平聚类
像k-means（如何弄到欧氏空间中是个问题，可以使用隐含空间模型，比如MDS），k-medoids什么的就很好，可以使用上面的相似度来聚类 。
2.2.3 谱聚类
图分割中的如 Ratio Cut和Normalized Cut其实和谱聚类是等价的（见参考3），所以谱聚类也能用在社区发现上。
2.3 分裂法
这里的分裂法和层次聚类中的类似，区别是前者不计算节点相似度，而是删除是两个社区之间的关联边，这些边上的两点的相似度不一定很低。其中最著名的算法就是Girvan-Newman算法，根据以下假设：社区之间所存在的少数几个连接应该是社区间通信的瓶颈，是社区间通信时通信流量的必经之路。如果我们考虑网络中某种形式的通信并且寻找到具有最高通信流量（比如最小路径条数）的边，该边就应该是连接不同社区的通道。Girvan-Newman算法就是这样，迭代删除边介数（Edge Betweenness）最大的边。
2.4 谱方法
基于谱分析的社区算法基于如下事实，在同一个社区内的节点，它在拉普拉斯矩阵中的特征向量近似。将节点对应的矩阵特征向量（与特征值和特征向量有关的都叫谱）看成空间坐标，将网络节点映射到多维向量空间去，然后就可以运用传统的聚类算法将它们聚集成社团。这种方法不可避免的要计算矩阵的特征值，开销很大，但是因为能直接使用很多传统的向量聚类的成果，灵活性很高。
2.5 基于模块度的方法
模块度不仅仅作为优化的目标函数提出，它也是目前是最流行的用来衡量社区结果好坏的标准之一（它的提出被称作社区发现研究历史上的里程碑)。我们知道，社区是节点有意识地紧密联系所造成的，它内部边的紧密程度总比一个随机的网络图来的紧密一些，模块度的定义就是基于此，它表示所有被划分到同一个社区的边所占的比例，再减除掉完全随机情况时被划分到同一个社区的边所占的比例： \[Q=\sum^K_{c=1}[\frac{A(V_i,V_i)}{m}-(\frac{degree(V_i)}{2m})^2]\] 其中\(V_i\)是第\(i\)个社区，\(m\)是整个图中边的数目。模块度的一个优点是好坏与社区中点的数目无关。模块度真是个好东西，第一次对社区这个模糊的概念提出了量化的衡量标准（不过据说对于小粒度的不太准）。所以对模块度的算法优化多种多样，从贪心到模拟退火等应有尽有。
2.6 动态算法
自旋模型和同步算法应该是物理学家提出来的算法（完全看不懂），话说物理学家在社区发现领域十分活跃，发了不少论文。随机游走是基于以下思想：如果存在很强的社区结构，那么随机游走器（random walker)会在社区内部停留更长的时间，因为社区内部的边密度比较高。
2.7 基于统计推断的算法
基于统计推断的方法包括观察到的数据集和对模型的假设。如果数据集是图，模型假设对节点之间如何联系的描述就要符合真实的图结构。
2.8 其他
个人觉得重叠和动态社区都很难成为一个类别，因为具体算法各有不同，用共同点“重叠”或“动态”来作为一类又太广泛了，比较适合作为特征或维度来描述。 而Web社区特指Web页面相互连接而成的集合,这又是一个大类，底下有不少算法。
3. 社区发现算法特征
下面我从不同的角度来描绘社区发现算法的一些特征（叫维度比较好？），这些特征可以用来对社区发现算法进行分类：
3.1 优化目标
有一些社区发现算法比如谱方法，KL算法，以及基于最大流的社区发现方法等，给出明确的的目标函数，并提出算法来最优化目标函数。 常用的优化目标函数有：
3.1.1 Normailized Cut和conductance
如果我们将图划分为\(S\)和\(\bar{S}=V-S\)两个部分，那么\(S\)与图中的剩下部分联系越少，说明\(S\)越独立，越有可能是一个内部紧密的社区。我们用\(cut(S)\)来表示两者 之间的联系数目： \[cut(S)=\sum_{i\in S,j\in \bar{S}}A(i,j)\] 为了避免孤立节点的产生，我们分别除以它的权值（内部度数之和），来达到相对平均一些的分割。这就是Normailized Cut: \[Ncut(S)=\frac{\sum_{i\in S,j\in \bar{S}}A(i,j)}{\sum_{i\in S}degree(i)}+\frac{\sum_{i\in S,j\in\bar{S}}A(i,j)}{\sum_{j\in \bar{S}}degree(j)}\] 连通度(conductance)也是类似的定义: \[ Conductance(S)=\frac{\sum_{i\in S,j\in \bar{S}}A(i,j)}{\min{(\sum_{i\in S}degree(i),\sum_{j\in\bar{S}}degree(j))}}\] 当涉及到多个划分\(V_1,\ldots,V_k\)时，Normalilized Cut和连通度就是它们之和。
3.1.2 Kernighan-Lin object
KL目标函数旨在使两个相同大小的社区之间的边联系最小： \[KLObj(V_1,\ldots,V_k)=\sum_{i\neq j}A(V_i,V_j)\] 其中\(A(V_i,V_j)=\sum_{u \in V_i,v \in V_j}A(u,v), |V_1|=|V_2|=\ldots=|V_k|\)。
3.1.3 Modularity
模块度在2.5已提过，这里就不说了。
3.2 粒度控制（社区数目可不可控）
对于有层次的社区发现算法来说的，比如某些二分社区算法，是通过不断递归的划分子社区来获得预定的社区数目。而某些算法，像层次聚类和MCL，基于概率模型的社区发现算法等，允许用户通过调节参数来间接控制输出社区的数目。
另一些算法，像模块度优化算法，它的社区数目是由优化函数决定的，不需要用户来设定社区的数目。
3.3 规模
很多算法在设计的时候，并没有特别地考虑伸缩性，在面对整个Web以及大型社交网络时动辄百万甚至千万个点时效果不佳。比如GN算法，需要计算即通过每条边的最短路径数目（edge betweeness)，复杂度相当高，像谱聚类算法，能处理10K个点和70M条边就不错了。
所以，有些算法比如Shingling算法等，使用的方法相对简单，从而能适合大规模的社区发现的运行要求。
3.4 局部社区发现
所谓的局部社区发现，是指只根据临近的邻居节点发现社区结构，而不考虑全局的网络，这与全局社区发现中对图中的每一个节点都打上社区标签的做法相对应。
在整个网络图很大，数据集不能全部加载到内存时，使用局部社区发现可以只加载图的一部分，发现一个局部社区，然后迭代地调用该方法来逐一地提取社区结构。
3.5 重叠社区
很多社区发现算法，比如图分割算法，将整个网络划分为多个独立的社区结构。但是在现实中，许多网络并不存在绝对的彼此独立的社团结构，相反，它们是由许多彼此重叠互相关联的社团构成，比如说在社交网络中，一个人根据兴趣的不同，有可能属于多个不同的小组等。所以，很多类似派系过滤算法（CPM）这样旨在发现重叠社区的算法也被不断地提出来。
3.6 动态社区发现
在4.1有讲，这里就不讲了。
3.7 评价标准（待改）
社区发现算法常用的评价标准有：
3.7.1 准确率，召回率，F1值
一个大规模数据集合中检索文档的时，可把文档分成四组：系统检索到的相关文档（A），系统检索到的不相关文档（B），相关但是系统没有检索到的文档（C），不相关且没有被系统检索到的文档（D）： 准确度定义为： \[pr=\frac{A}{A+C}\] 召回率定义为： \[rc=\frac{A}{A+B}\] F-measure是准确率和召回率协调之后的结果，定义为： \[PWF=\frac{2\times pr \times rc}{pr+rc}\] 同理，社区也可以用这个概念。
3.7.2 平均聚类纯度
平均聚类纯度，average cluster purity。假设算法发现了\(C=\{C_1,\ldots,C_K\}\)个社区，我们假设社区\(C_i\)有\(n_i\)个点，每个点分别为\(\{v_{1,i},\ldots,v_{n_i,i}\}\)。令\(M_{l,i}\)为点\(v_{l,i}\) 真实归属的标签，平均聚类纯度为定义为 \[ACP=\frac{1}{k}\sum_{i=1}^k\sum_{l=1}^{n_i}\frac{\delta(dom_i\in M_{l,i})}{n_i}\] 即社区\(C_i\)中主要标签的点占社区所有点的数目比例。
3.7.3 互信息
首先来回顾熵的定义,在一个分布内包含的信息为熵： \[H(X)=-\sum_{x \in X}p(x)\log p(x)\] 互信息（mutual information)描述了两个分布之间的相关性 \[I(X;Y)=\sum_{y \in Y}\sum_{x \in X}p(x,y)\log(\frac{p(x,y)}{p(x)p(y)})\] 我们有 \[I(X;Y)=H(X)-H(X|Y)\] 所谓两个事件相关性的量化度量，就是在了解其中一个Y的前提下，对消除另一个X不确定性所提供的信息量。 规范化的互信息定义为 \[NMI(X;Y)=\frac{I(X;Y)}{\sqrt{H(X)H(Y)}}\] 我们将划分当做一个结点落在社区的概率分布吗，然后计算社区划分结果和真实情况的NMI值，具体例子见参考4.
4. 社区发现的趋势
4.1 动态社区发现 (Dynamic Networks)
很多社区算法都把社区看做静态的图，但是事实上的社交网络是随着时间逐渐演变的。这些社区如何形成和消解，它们的的动态变化该如何处理，确实是一个研究热点。
4.2 异构网络上的社区发现(Heterogeneous Network)
日常算法中我们都假定网络中的点和边属于同一类型。但是现实中也有很多异构网络（Heterogeneous Networks)它的点和边的类型不同。比如说IMDB网络，它的实体可能包括电影，导演，演员，而他们之间的关系也不同。如何在这样的网络上做社区发现也是一大挑战。
4.3 有向图上的社区发现(Directed Networks)
一般的社区发现都把整个网络当做无向图来处理。但是很多网络它的有向性比较特殊，比如说Web社区，论文之间的引用关系，以及Twitter用户之间的关注关系。简单地忽略这些网络中的方向性，会导致信息的损失，算法可能会得出错误的结果。
4.4 内容与链接关系结合的社区发现(Content and Relationship Information)
像前面说过的一样，新兴社交网络中的关系，不仅仅再是一条有向边，其中可以包括很多内容信息（文本，图像，地理信息），这又将社区发现带向了新的领域——如何联合这些关系和内容信息来发现社区。
4.5 交叉领域的社区发现(Crosscutting Issues)
伸缩性。比如说并行和分布式算法，利用GPU来运算等。
可视化。如何展示数以十亿计节点，以及如何处理动态信息。
交叉领域上的社区发现。生物学什么的。
做排名。
总而言之结论就是，社区发现（特别是社交网络上的）还是比较新的，还是有一大把理论上和实践上的开放问题可做的。（我才不信呢>_<！）
参考文献：
1. Fortunato, S. (2010). “Community detection in graphs.” Physics Reports 486(3): 75-174.
2.《 Social Network Data Analytics》第四章，DOI 10.1007/978-1-4419-8462-3_4
3.http://blog.pluskid.org/?p=287
4.《社会计算：社区发现和社会媒体挖掘》,Page 58